package 笔试.bilibili笔试.第三题找零;
//1024块钱，最少找1,4，16,64的多少个硬币
public class Solution
{
    public static int GetCoinCount (int N)
    {
        int n=1024-N;
        int[] money=new int[]{1,4,16,64};
        int[] dp=new int[n+1];//为什么n+1.索引代表给出多少钱，对应的值dp[i]是对应的最少的钱币个数，多了一个0元的情况
        dp[0]=0;
        for (int i = 1; i < n + 1; i++)
        {
            dp[i]=Integer.MAX_VALUE;
            for (int j = 0; j < money.length; j++)
            {
                if (i-money[j]>=0)
                    dp[i]=Math.min(dp[i],dp[i-money[j]]+1);
            }
        }
        return dp[n];
    }

    public static void main(String[] args)
    {
        System.out.println(GetCoinCount(1016));
    }
}
